package day_2022_7_to_8.day48;

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * @author haomin
 * @date 2022/08/21 11:22
 **/
public class Day36_4_Num6166_LargestPalindromic {
    public static void main(String[] args) {
        //System.out.println(isReverse("4444"));
        System.out.println(largestPalindromic("00009"));
    }
    public static List<String> list = new LinkedList<>();
    public static String largestPalindromic(String num) {
        int[] flag = new int[num.length()];
        StringBuffer sb = new StringBuffer();
        dfs(num, flag, sb);
        String res= "";
        Collections.sort(list);
        for (String s : list) {
            if(s.length() >= res.length()){
                res = s;
            }
        }
        int i = 0,j = res.length()-1;
        while(i < j && res.charAt(i) == '0' && res.charAt(j) =='0'){
            res = res.substring(i+1,j);
            i = 0;j = res.length()-1;
        }
        return res;
    }

    private static void dfs(String num, int[] flag, StringBuffer sb) {
        if(isReverse(sb.toString())){
            if(!list.contains(sb.toString())) {
                list.add(sb.toString());
            }
        }
        for(int i = 0; i < num.length(); ++i){
            if(flag[i] == 1) continue;
            sb.append(num.charAt(i)); flag[i] = 1;
            dfs(num,flag,sb);
            sb.deleteCharAt(sb.length()-1); flag[i] = 0;
        }
    }

    private static boolean isReverse(String str) {
        StringBuffer sb = new StringBuffer(str).reverse();
        return sb.toString().equals(str);
    }

}